require("node")
require("stack")

module(..., package.seeall )

local metaTable = {
	__index = getfenv()
}

function New( nodelist, directed )

	local o = {
		nodes = {}	
	}
	
	setmetatable( o, metaTable )
	
	if directed then
		o:addDirectedNodes( nodelist )
	else
		o:addUndirectedNodes( nodelist )
	end
	
	return o
	
end

function getNode( self, id )
	
	if self.nodes[ id ] == nil then
		
		local newNode = node.New( id )
		
		self.nodes[ id ] = newNode
		
		return newNode
		
	end
	
	return self.nodes[ id ]
	
end

function addUndirectedNodes( self, nodelist )
	
	for k, v in ipairs( nodelist ) do
		
		local node = self:getNode( k )
		
		for _, v2 in ipairs( v ) do
			node:addUndirectedNeighbor( self:getNode( v2.dst ) )
		end
		
	end	

end

function addDirectedNodes( self, nodelist )
	
	for k, v in ipairs( nodelist ) do
		
		local node = self:getNode( k )
		
		for _, v2 in ipairs( v ) do
			node:addDirectedNeighbor( self:getNode( v2.dst ) )
		end
		
	end	

end

function hasCycle( self )

	local usedNodes = {}
	local activeStack = stack.New()
	
	local function findCycle( node )
		
		activeStack:push( node )
		
		for _, neighbor in pairs( node.neighbors ) do
		
			if not table.contains( usedNodes, node ) then
				table.insert( usedNodes, neighbor )
			end
			
			if activeStack:has( neighbor ) then
				error("Cycle found on node: " .. tostring( activeStack ) .. tostring(neighbor) )
			end
			
			findCycle( neighbor )
			
		end
		
		activeStack:pop()
		
	end
	
	--Find a node that is not a in a graph yet
	for key, node in pairs( self.nodes ) do
		
		if not table.contains( usedNodes, node ) then
			table.insert( usedNodes, node )
		end
		
		local b, err = pcall( findCycle, node )
		
		if not b then
			return false, err
		end
		
	end
	
	return true

end